package com.company;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//给你一个产品数组 products 和一个字符串 searchWord ，products  数组中每个产品都是一个字符串。
//
//请你设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。
//
//请你以二维列表的形式，返回在输入 searchWord 每个字母后相应的推荐产品的列表
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/search-suggestions-system
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
public class Leetcode1268 {

    public static void main(String[] args) {
        // write your code here
        String[] products = {"havana"};
        String searchWord = "tatiana";
        System.out.println(suggestedProducts(products, searchWord));
    }

    public static List<List<String>> suggestedProducts(String[] products, String searchWord) {
        //先排序
        Arrays.sort(products);
        //所有的结果
        List<List<String>> allResult = new ArrayList<>();
        for (int i = 1; i <= searchWord.length(); i++) {
            //依次取得前缀
            String s = searchWord.substring(0, i);
            //匹配的结果
            List<String> result = new ArrayList<>();
            int k = 0;
            for (int j = 0; j < products.length; j++) {
                //如果前缀相同,且超过3个，那就只返回3个
                if (products[j].indexOf(s) == 0 && k < 3) {
                    result.add(products[j]);
                    k++;
                }
            }
            allResult.add(result);
        }
        return allResult;
    }
}
